1. Field of the Invention
The present invention is related to an apparatus and a method for estimating a motion vector utilized to compensate for motion of an image in a prediction coding process of a moving picture.
2. Description of the Related Art
In a conventional method and apparatus for estimating a motion vector estimating method, a current picture to which a prediction coding process is performed is divided into a plurality of blocks, for example, to have 16 pixels in a horizontal direction and 16 pixels in a vertical direction. These blocks are referred to as current blocks. A search region is predetermined in a reference picture for each of the above-described current blocks to have as a center of the search region the positions corresponding to the horizontal position and the vertical position of a pixel position of each current block. The predetermined search region in the reference picture is referred to as a search window. A block matching process is carried out between a specific one of the current blocks and the search window corresponding to the specific current block to estimate a position on which a predetermined evaluation function has the minimum value for obtaining a motion vector. The conventional motion vector estimating apparatus is directed to a purpose that the motion vector can be more correctly obtained.
A first conventional example of a motion vector estimating apparatus is disclosed in, for example, Japanese Laid Open Patent Application (JP-A-Showa 61-201583). In the reference, a limit value is provided to limit a reference region used to search the motion vector in accordance with a change amount of a motion vector detected in a previous frame to a current frame. When the motion vector change amount exceeds the limit value, this limit value is outputted.
Also, a second conventional example of the motion vector estimating apparatus is proposed in Japanese Laid Open Patent Application (JP-A-Heisei 5-328333), in which several search windows or regions for a motion vector are prepared to be different from each other in position. One of the several reference windows or regions is selected in accordance with the change amounts of the motion vectors detected in a previous frame to the current frame.
Further, a third conventional example of the motion vector estimating apparatus is proposed in Japanese Laid Open Patent Application (JP-A-Heisei 7-203457), in which an accumulating process of absolute values of differences is executed in a parallel manner in the block matching process. As a result, the capacity of a buffer for signals used in the accumulation is reduced so as to increase the processing speed.
Furthermore, a fourth conventional example of the motion vector estimating apparatus is proposed in Japanese Laid Open Patent Application (JP-A-Heisei 7-250328), in which motion vectors used to compensate for the moving image prediction are estimated in accordance with a plurality of prediction modes with a small hardware amount.
There are the following problems in the above-described conventional examples of the motion vector estimating techniques.
(1) The first problem is in the following point. That is, power consumption cannot be reduced in the first conventional example of the motion vector estimating apparatus in which the limit value is provided to limit the search region for the motion vector. This is because in the motion vector estimating apparatus described in Japanese Laid Open Patent Application (JP-A-Showa 61-201583), the limit value is only introduced to the reference region. The calculation time and the calculation amount for the block matching process to be executed cannot be reduced in actual. In other words, since the calculation time and the calculation amount cannot be reduced, the power consumption of the motion vector estimating apparatus cannot be reduced.
In the block matching process as described in, for instance, Japanese Laid Open Patent Application (JP-A-Heisei 7-203457) and Japanese Laid Open Patent Application (JP-A-Heisei 7-250328), the operation time is reduced by employing parallel processing. However, the reason why the operation time cannot be reduced is that if the limit value is provided as in the motion vector estimating apparatus described in Japanese Laid Open Patent Application (JP-A-Showa 61-201583), the parallel degree of the above-described parallel processing decreases. As a result, the operation time cannot be reduced.
(2) The second problem is in that the correct motion vector cannot be obtained in the conventional motion vector estimating apparatus as proposed in Japanese Laid Open Patent Application (JP-A-Heisei 5-328333), in which the several reference regions for the motion vector are prepared. This is because in the method for selecting the optimum reference region from the prepared reference regions, when pictures are such complex that more than one object move, the object moving direction cannot be exclusively determined. As a result, the optimum reference region cannot be selected from the prepared several reference regions.
Also, in the above-described motion vector estimating apparatus described in Japanese Laid Open Patent Application (JP-A-Heisei 5-328333), if the size and/or shape of the reference region cannot be previously determined, then the parallel degree of the apparatus for executing the block matching process would be lowered. As a consequence, since the shape of the reference region is limited and thus the proper reference region cannot be utilized, the correct motion vector cannot be obtained.
(3) The third problem is in that in the motion vector estimating apparatus proposed in Japanese Laid Open Patent Application (JP-A-Heisei 7-203457), the difference absolute value accumulating process is carried out in the parallel manner using the small buffer for signals for the calculation. However, in the motion vector estimating apparatus, the hardware amount of the block matching circuit for executing the difference absolute value accumulating process in the parallel manner increases so that the chip area for the block matching circuit is increased as well as the power consumption is increased. This is because in the motion vector estimating apparatus as described in Japanese Laid Open Patent Application (JP-A-Heisei 7-203457) and Japanese Laid Open Paten Application (JP-A-Heisei 7-250328), a large amount of wiring lines must be provided for a processing element as the minimum unit of the block matching circuit. Thus, the valid data can be continuously entered into the respective processing elements such that the parallel degree is increased. As a consequence, a chip area required for the wiring lines increases considerably.
Also, in the above-explained motion vector estimating apparatus described in Japanese Laid Open Patent Application (JP-A-Heisei 7-203457) and Japanese Laid Open Patent Application (JP-A-Heisei 7-250328), there is another problem. That is, the minimum value determining unit determines the minimum value of a summation of absolute values of differences accumulated values in the respective processing elements, and the chip area required for wiring lines is considerably increased, because a total number of wiring lines is very large which are used to be connected from the minimum value determining unit.
(4) The fourth problem is in that if the size and/or shape of the reference region is allowed to be varied in the motion vector estimating apparatus in which the difference absolute value accumulating process is in the parallel manner, the hardware amount of the block matching circuit for executing the difference absolute value accumulation process in the parallel manner is increased. As a result, the chip area increases and also the power consumption increases. Also, at this time, the parallel degree is reduced. This is because the large amount of wiring lines must be provided to continuously enter the valid data into the processing elements as the minimum unit for constituting the block matching circuit.
Also, it is because the data entering sequence of the processing element is greatly changed, depending upon the sizes and the shapes of the reference regions. As a result, the process for reading out the reference data from a storage unit becomes complex, so that the chip area increases and the power consumption increases.
(5) The fifth problem is in that the chip area of the block matching circuit increases in the motion vector estimating apparatus in which the motion vector is estimated in a plurality of prediction modes. This is because a large number of wiring lines is required to connect the minimum value determining unit for determining the minimum value of the difference absolute value accumulated values to the respective processing elements in the motion vector estimating apparatus described in Japanese Laid Open Patent Application (JP-A-Heisei 7-250328). As a result, the chip area required for the wiring lines is considerably increases.
Also, the stage number of FIFOs (first-in first-out) required for the block matching circuit is increased.
As a consequence, the present invention has been made to solve the above-described problems. Therefore, an object of the present invention is to provide a motion vector estimating method and a motion vector estimating apparatus which can estimate a motion vector in high precision with low power consumption and a saved chip area.
Another object of the present invention is to provide a motion vector estimating method and a motion vector estimating apparatus, in which when a parallel processing is applied to a block matching process, the parallel degree thereof is not reduced.
Still another object of the present invention is to provide a motion vector estimating method and a motion vector estimating apparatus, in which motion vectors of a plurality of prediction modes can be estimated while saving the chip area of a block matching circuit.
Yet still another object of the present invention is provide a motion vector estimating apparatus, which can be realized with the saved chip area of a block matching circuit regardless of the dimension and shape of a reference region.
In order to achieve an aspect of the present invention, a motion vector estimating apparatus includes a current picture storage unit which stores image data of a current picture, a reference picture storage unit which stores image data of a reference picture, a search window determining unit which determines estimation history from previously estimated motion vectors, and determines a search window based on the estimation history, wherein the search window is composed of rectangular reference regions, a block matching circuit for performing a block matching process to a current block and each of reference blocks of the search window to determine a motion vector, and a control circuit which reads out the image data of the current block from the current picture storage unit to supply the block matching circuit, which reads out the image data of each of the reference blocks of the search window from the reference picture storage unit to supply to the block matching circuit, and which controls the block matching circuit such that the block matching process is performed to the current block and the each reference block of the search window.
At least one of a shape of the search window, a size of the search window and a position of the search window is determined based on the estimation history.
The search window determining unit determines whether the number of previously estimated motion vectors exceeds a predetermined number. When it is determined that the number of previously estimated motion vectors is less than the predetermined number, the search window determining unit neglects the previously estimated motion vectors and determines optimal size and shape of the search window. On the other hand, when it is determined that the number of previously estimated motion vectors exceeds the predetermined number, the search window determining unit produces a 2-dimensional map in which each of the previously estimated motion vectors is mapped based on its horizontal value and the vertical value. Thus, the search window determining unit determines optimal size and shape of the search window such that the search window includes the history of the previously estimated motion vectors. Also, the search window determining unit calculates average values of changes of the previously estimated motion vectors in the horizontal and vertical directions, respectively, and determines an optimal position of the search window such that, for example, a center position of the search window is shifted based on the average values. In this manner, the size, shape and position may be independently determined. On the contrary, the size, shape and position may be collectively determined.
The motion vector estimating apparatus may further include a load detecting circuit for detecting either one of a load of the motion vector estimating apparatus or a load of the block matching circuit. In this case, the search window determining unit determines the search window based on the estimation history and the detected load. Also, the motion vector estimating apparatus may further include a voltage detecting circuit for detecting a power supply voltage. In this case, the search window determining unit determines the search window based on the estimation history and the detected power supply voltage. Further, the motion vector estimating apparatus may further include a temperature detecting circuit for detecting a temperature of a chip on which the block matching circuit is installed. In this case, the search window determining unit determines the search window based on the estimation history and the detected temperature. In addition, the search window determining unit may determine at least an unuseful region in the search window in unit of pixels based on the estimation history, and set a flag to each of pixels of the unuseful region such that the block matching process to the reference block which includes any pixel of the unuseful region is made invalid based on the flag of the pixel of the unuseful region.
The block matching circuit includes processing elements of M columns and N rows (M and N are positive integers) provided such that a likelihood between the current block and each of the reference blocks is calculated through pipeline processing. In this case, the block matching circuit may further include a hierarchical selector structure such that each of the processing elements is supplied with one of the pixel data of each of the reference blocks. Also, the block matching circuit may further include (M+N) reference data buses, which are provided for the M columns and the N rows, and N current data buses provided for the N rows, respectively. In this case, each of the (M+N) reference data buses transfers one pixel data of any of the reference blocks in a unit time of the pipeline processing. The current block is composed of M columns and N rows.
The processing elements may be cascade-connected in each of the N rows and the N rows may be cascade-connected.
In another case, the processing elements may be cascade-connected in each of the N rows (N is an even number). Odd-numbered ones of the N rows in an upper half are cascade-connected via first FIFO units, each of which is provided for two adjacent odd-numbered rows, wherein even-numbered ones of the N rows in the upper half are cascade-connected via second FIFO units, each of which is provided for two adjacent even-numbered rows, wherein odd-numbered ones of the N rows in a lower half are cascade-connected via third FIFO units, each of which is provided for two adjacent odd-numbered rows, and wherein even-numbered ones of the N rows in the lower half are cascade-connected via fourth FIFO units, each of which is provided for two adjacent odd-numbered rows. Further, the block matching circuit further includes fifth and sixth FIFO units connected to last stages of processing elements in the cascade connections for the odd-numbered rows and the even-numbered rows in the upper half, respectively. In this case, a number of stages in each of the first to fourth FIFO units is M, and a number of stages in the fifth FIFO unit is (Mxc3x97N/2+M), and a number of stages in the sixth FIFO unit is (Mxc3x97N/2).
In order to achieve another aspect of the present invention, a motion vector estimating apparatus includes processing elements of M columns and N rows (M and N are positive integers), wherein the processing elements are cascade-connected in each of the N rows, wherein each of the processing elements calculates an absolute value of a difference between a corresponding pixel data of a current block and one pixel data of each of reference blocks, and adds the absolute value to an output from a previous stage of processing element to output the adding result to a next stage of processing element, and wherein the N rows are cascade-connected to allow pipeline processing, M reference data column buses provided for the M columns, respectively, N reference data row buses provided for the N rows, respectively, (Mxc3x97N) selectors, which are respectively provided for the processing elements to allow one of the pixel data on the corresponding one of the M reference data column buses and the pixel data on the corresponding one of the N reference data row buses to the corresponding processing element as the reference block pixel data, and a current block pixel data bus for transferring current block pixel data to each of the processing elements.
The motion vector estimating apparatus may further includes a reference block data bus group for transferring pixel data of the reference blocks in units of rows as sequences of pixel data, a first group of selectors which are respectively provided for the M reference data column buses, and each of which selects one pixel data of one of the sequences to supply to the corresponding reference data column bus, and a second group of selectors which are respectively provided for the N reference data row buses, and each of which selects one pixel data of one of the sequences to supply to the corresponding reference data row bus. In this case, each of the processing elements latches the corresponding current block pixel data once the corresponding current block pixel data is supplied via the current block pixel data bus. Also, each of the processing elements is synchronized with a clock signal to perform the calculation of the absolute value of the difference and the addition and to output the addition result to the next stage of processing element. Thus, the processing elements calculates a likelihood of one of the reference blocks in a time period from a first time to (Mxc3x97N) time, and calculates a likelihood of a different one of the reference blocks in a time period from a second time to (Mxc3x97N+1) time.
The current block is composed of pixels of M columns and N rows.
In a case, the processing elements are cascade-connected in each of the N rows and the N rows are cascade-connected.
In another case, the processing elements are cascade-connected in each of the N rows (N is an even number). In addition, odd-numbered ones of the N rows in an upper half are cascade-connected via first FIFO units, each of which is provided for two adjacent odd-numbered rows, even-numbered ones of the N rows in the upper half are cascade-connected via second FIFO units, each of which is provided for two adjacent even-numbered rows, odd-numbered ones of the N rows in a lower half are cascade-connected via third FIFO units, each of which is provided for two adjacent odd-numbered rows, and even-numbered ones of the N rows in the lower half are cascade-connected via fourth FIFO units, each of which is provided for two adjacent odd-numbered rows. Also, the block matching circuit further includes fifth and sixth FIFO units connected to last stages of processing elements in the cascade connections for the odd-numbered rows and the even-numbered rows in the upper half, respectively. In this case, a number of stages in each of the first to fourth FIFO units is M, and a number of stages in the fifth FIFO unit is (Mxc3x97N/2+M), and a number of stages in the sixth FIFO unit is (Mxc3x97N/2+). The motion vector estimating apparatus may further include a fist adder adding an output of the fifth FIFO unit and an output of the sixth FIFO unit, a second adder adding the output of the fifth FIFO unit and an output of the processing element in a last stage of odd-numbered cascade connection in the lower half, a third adder adding the output of the sixth FIFO unit and an output of the processing element in a last stage of even-numbered cascade connection in the lower half, a fourth adder adding the output of the processing element in the last stage of odd-numbered cascade connection in the lower half and the output of the processing element in the last stage of even-numbered cascade connection in the lower half, and a fifth adder adding an output of the second adder and an output of the third adder.
In still another case, the processing elements are cascade-connected in each of the N rows (N is an even number). Also, ones of the N rows in an upper half are cascade-connected via first FIFO units, each of which is provided for two adjacent rows, and ones of the N rows in a lower half are cascade-connected via second FIFO units, each of which is provided for two adjacent rows. In addition, the block matching circuit further includes a third FIFO units connected to the processing element in a last stage of cascade connection in the upper half. In this case, a number of stages in each of the first and second FIFO units is M, and a number of stages in the third FIFO unit is (Mxc3x97N/2). The motion vector estimating apparatus may further include an adder adding an output of the third FIFO unit and an output of the processing element in a last stage of cascade connection in the lower half.
In yet still another case, the processing elements are cascade-connected in each of the N rows (N is an even number). Also, odd-numbered ones of the N rows are cascade-connected via first FIFO units, each of which is provided for two adjacent odd-numbered rows, and even-numbered ones of the N rows are cascade-connected via second FIFO units, each of which is provided for two adjacent even-numbered rows. In this case, a number of stages in each of the first and second FIFO units is M. The motion vector estimating apparatus may further include an adder adding an output of the processing element in a last stage of odd-numbered cascade connection and an output of the processing element in a last stage of even-numbered cascade connection.
In order to achieve still another aspect of the present invention, a method of estimating a motion vector, includes the steps of:
determining estimation history from previously estimated motion vectors;
determining a search window based on the estimation history, wherein the search window is composed of rectangular reference regions; and
performing a block matching process to a current block and each of reference blocks of the search window to determine a motion vector.